package practice_2025_7_28;

class Solution {
    /**
     * 不同路径II
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        // 创建dp表
        int[][] dp = new int[m+1][n+1];
        // 初始化
        dp[0][1] = 1;
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                if(obstacleGrid[i - 1][j - 1] != 1) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
        }
        return dp[m][n];
    }

    /**
     * 下降路径最小和
     * @param matrix
     * @return
     */
    public int minFallingPathSum(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        // 创建dp表
        int[][] dp = new int[m+1][n+2];
        // 初始化
        for(int i = 1; i <= m; i++) {
            dp[i][0] = Integer.MAX_VALUE;
            dp[i][n + 1] = Integer.MAX_VALUE;
        }
        // 填表
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
            }
        }
        // 返回
        int res = dp[m][1];
        for(int j = 2; j <= n; j++) {
            res = Math.min(res, dp[m][j]);
        }
        return res;
    }
}